package 每日一题;

import java.util.HashSet;
import java.util.Set;

public class No567字符串的排列 {

    /**
     * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
     * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
     *
     * 示例1:
     * 输入: s1 = "ab" s2 = "eidbaooo"
     * 输出: True
     * 解释: s2 包含 s1 的排列之一 ("ba").
     *  
     * 示例2:
     * 输入: s1= "ab" s2 = "eidboaoo"
     * 输出: False
     *
     * 注意：
     * 输入的字符串只包含小写字母
     * 两个字符串的长度都在 [1, 10,000] 之间
     */

    //参考着写出来的,还是不够熟练
    public boolean checkInclusion(String s1, String s2) {

        Set<Character> set=new HashSet<>();
        //双while循环
        int[] frep=new int[26];
        char[] s1Arr = s1.toCharArray();
        int count=0;
        for (char c : s1Arr) {
            if(frep[c-'a']==0){
                count++;
            }
            frep[c-'a']++;
            set.add(c);
        }

        int left=0;
        int right=0;

        while (right<s2.length()){

            //如果 计数大于0=>right右移动
            char cRight = s2.charAt(right);
            if(set.contains(cRight)){
                frep[cRight-'a']--;
                if(frep[cRight-'a']==0){
                    count--;
                }
            }
            right++;
            if (right-left>=s1.length()){
                if(count==0){
                    return true;
                }
                //移动左指针 维护count
                char cLeft = s2.charAt(left);
                if(set.contains(cLeft)){
                    if(frep[cLeft-'a']==0){
                        count++;
                    }
                    frep[cLeft-'a']++;
                }
                left++;
            }
        }
        return false;
    }

    public boolean checkInclusion2(String s1,String s2) {

        Set<Character> set=new HashSet<>();
        int[] frep=new int[26];
        int count=0;
        for (char c : s1.toCharArray()) {
            if(frep[c-'a']==0){
                count++;
            }
            frep[c-'a']++;
            set.add(c);
        }

        int left=0;
        int right=0;

        while (right<s2.length()){

            char cRight=s2.charAt(right);
            right++;

            if(set.contains(cRight)){
                frep[cRight-'a']--;
                if(frep[cRight-'a']==0){
                    count--;
                }
            }

            //答案必在这一个窗口内,所以只认这个窗口,进了其他字符也不要紧
            if (right-left>=s1.length()){

                if(count==0){
                    return true;
                }

                char cLeft=s2.charAt(left);
                if(set.contains(cLeft)){
                    if(frep[cLeft-'a']==0){
                        count++;
                    }
                    frep[cLeft-'a']++;
                }
                left++;
            }

        }

        return false;
    }

    public static void main(String[] args) {
        No567字符串的排列 n=new No567字符串的排列();
        boolean result = n.checkInclusion2("ab", "eidaboaoo");
        System.out.println(result);
    }

}
